Introductory Remarks -------------------- What's an algorithm? Set of instructions the computer will follow to solve a problem Suppose you need an algorithm to solve a particular problem. If there are several competing algorithms, each of which solves the problem correctly, how do you go about choosing the particular algorithm you will use in your program? It depends on what you are trying to optimize 1. Running time 2. Memory or disk space 3. Programmer time Rules of thumb: 1. Memory and disk space are cheap 2. Use the simplest algorithm that meets your requirements 3. Often there is tension between simplicity and efficiency 4. Start simple, only add complexity when needed How do you measure the running time of an algorithm? Two approaches: 1. Empirical a. Implement all of the candidate algorithms b. Run each on all possible inputs (if feasible) c. Alternatively, pick a representative set of inputs (benchmark) and run each algorithm on the benchmark 2. Theoretical a. Mathematically analyze each algorithm on paper b. Predict performance on expected inputs How does input size affect running time? Clearly, sorting 10000 items should take longer than sorting only 10 items Define T(N) to be the number of time units an algorithm uses given an input of size N What's T(N) for the following method? (Assume each statement uses exactly one time unit) double mean (double[] a, int n) { double sum = 0; for (int i = 0; i < n; i++) sum += a[i]; double mean = sum / count; return mean; } T(N) = 1 + 1 + (n+1) + n + n + 1 + 1 = 3n + 5 A Closer Look at T(N) --------------------- Suppose you have T(N) = N^2 + 2N + 4 Does it make sense to define T(N) this precisely? NO 1. When N is large, the high-order term dominates N^2 + 2N + 4 = 1002004 when N is 1000 2. When N is small, time is not an issue 3. Constant factors depend on machine and compiler How do you capture the dominant term of T(N)? 1. Use BigOh notation 2. Abstraction of time formula 3. Keep the dominant term 4. Drop low-order terms 5. Drop constants Formal definition T(N) is O(f(N)) if there exist positive constants c and N0, such that T(N) <= c.f(N) for all N >= N0 Some examples of bad BigOh style 1. O(2N) --> O(N) 2. O(N + 2) --> O(N) 3. O(N^2 + N) --> O(N^2) Common BigOh Functions O(1) constant (example: input N, print "hello world") O(log N) logrithmic (example: phone book search, trade-off sort/search) O(N) linear O(NlogN) NlogN O(N^2) quadratic O(N^3) cubic O(2^N) exponential Note: See Chapter 5 if you need a refresher on the log function. Finding the BigOh of an Algorithm --------------------------------- What's the Running Time of a single statement? O(1) What's the Running Time of a number of sequential statements? O(f1(n) + f2(n) + ... + fk(n)) What's the Running Time of a selection statement? The larger of O(f1(n)) and O(f2(n)) where f1(n) is the running time of the if part and f2(n) is the running time of the else part What's the Running Time of a Loop? O(f(n)*g(n)) where f(n) is the running time of the statements in the loop and g(n) is the number of iterations Class Exercise -------------- Give a BigOh analysis of the running time for each program fragment (This is problem 5.15a) for ( int i = 0; i < n; i++ ) sum++; for ( int i = 0; i < n; i += 2 ) sum++; for ( int i = 0; i < n; i++ ) for ( int j = 0; j < n; j++ ) sum++; for ( int i = 0; i < n; i++ ) sum++; for ( int j = 0; j < n; j++ ) sum++; for ( int i = 0; i < n; i++ ) for ( int j = 0; j < n*n; j++ ) sum++; for ( int i = 0; i < n; i++ ) for ( int j = 0; j < i; j++ ) sum++; for ( int i = 0; i < n; i++ ) for ( int j = 0; j < n*n; j++ ) for ( int k = 0; k < j; k++ ) sum++; Give the BigOh analysis of the following program. public static int fSearch( int [ ] a, int x ) { int low = 0; int high = a.length - 1; int mid; while( low <= high ) { mid = ( low + high ) / 2; if( x > a[ mid ] ) low = mid + 1; else if( x < a[ mid ] ) high = mid - 1; else return mid; } return NOT_FOUND; // NOT_FOUND = -1 } Show the steps of fSearch([1 2 4 5 6 8 9], 6). Show the steps of fSearch([1 5 3 8 2 4 7], 3). What assumption does fSearch make about the input array? (a) BinSearch (compare sequential and binary searches) Working Through a More Elaborate Example ---------------------------------------- Maximum Contiguous Subsequence Sum Given a sequence of integers, find a subsequence that gives the maximum sum What's the simplest solution? 1. Compute the sum of every possible subsequence 2. Store the largest sum public static int maxSubSum1( int [ ] a ) { int maxSum = 0; for( int i = 0; i < a.length; i++ ) for( int j = i; j < a.length; j++ ) { int thisSum = 0; for( int k = i; k <= j; k++ ) thisSum += a[ k ]; if( thisSum > maxSum ) { maxSum = thisSum; seqStart = i; seqEnd = j; } } return maxSum; } What's the BigOh for this algorithm? (a) MaxSumTest (running time of cubic MaxSubSum) How large of a problem can you solve before the algorithm starts to slow down? Can we make the algorithm faster? 1. Remove a loop 2. The subsequence sum is the previous sum plus one item public static int maxSubSum2( int [ ] a ) { int maxSum = 0; for( int i = 0; i < a.length; i++ ) { int thisSum = 0; for( int j = i; j < a.length; j++ ) { thisSum += a[ j ]; if( thisSum > maxSum ) { maxSum = thisSum; seqStart = i; seqEnd = j; } } } return maxSum; } What's the BigOh for this algorithm? (b) MaxSumTest (running time of quadratic MaxSubSum) How large of a problem can you solve before the algorithm starts to slow down? Can we make the algorithm even faster? 1. Remove another loop 2. Details left out (see Chapter 5) public static int maxSubSum3( int [ ] a ) { int maxSum = 0; int thisSum = 0; for( int i = 0, j = 0; j < a.length; j++ ) { thisSum += a[ j ]; if( thisSum > maxSum ) { maxSum = thisSum; seqStart = i; seqEnd = j; } else if( thisSum < 0 ) { i = j + 1; thisSum = 0; } } return maxSum; } What's the BigOh for this algorithm? (c) MaxSumTest (running time of linear MaxSubSum) How large of a problem can you solve before the algorithm starts to slow down? Comparison of Growth Rates -------------------------- How do linear, quadratic, and cubic growth rates compare when given inputs of increasing size? If an algorithm takes 1 second to solve a problem of size 10, how long does it take to solve a problem of size 1000? Linear (T(N) = c*N) T(1000)/1000 = T(10)/10 T(1000)/1000 = 1/10 T(1000) = 1000/10 T(1000) = 100 Quadratic (T(N) = c*N^2) T(1000)/(1000^2) = T(10)/(10^2) T(1000)/(1000*1000) = 1/(10*10) T(1000) = (1000*1000)/(10*10) T(1000) = 100*100 = 10000 Cubic (T(N) = c*N^3) T(1000)/(1000^3) = T(10)/(10^3) T(1000)/(1000*1000*1000) = 1/(10*10*10) T(1000) = (1000*1000*1000)/(10*10*10) T(1000) = 100*100*100 = 1000000 If an algorithm takes 10 seconds to solve a problem of size 100, how large a problem can it solve in 1000 seconds? Linear (T(N) = c*N) N/T(N) = 100/T(10) N/1000 = 100/10 N = 1000*100/10 N = 10000 Quadratic (T(N) = c*N^2) (N^2)/T(N) = (100^2)/T(10) (N^2)/1000 = (100*100)/10 (N^2) = 1000*(100*100)/10 (N^2) = 1000000 N = 1000 Cubic (T(N) = c*N^3) (N^3)/T(N) = (100^3)/T(10) (N^3)/1000 = (100*100*100)/10 (N^3) = 1000*(100*100*100)/10 (N^3) = 100000000 N = 100 * cube-root(100) (4.65) Suppose you have 1000 seconds and the coefficient of the dominant term in T(N) is 10^-9 seconds (A CPU this fast may exist in the next 5-10 years). How large a problem can you solve? Linear (T(N) = c*N) 1000 = 10^-9 * N N = 1000 / 10^-9 N = 10^12 could work up to about a trillion Quadratic (T(N) = c*N^2) 1000 = 10^-9 * N^2 N^2 = 1000 / 10^-9 N^2 = 10^12 N = 10^6 could work up to about a million Cubic (T(N) = c*N^3) 1000 = 10^-9 * N^3 N^3 = 1000 / 10^-9 N^3 = 10^12 N = 10^4 could work up to about 10 thousand What's the expected increase in time if N doubles in size? Linear 2 times Quadratic 4 times Cubic 8 times Checking an Algorithm Analysis ------------------------------ How can you check an algorithm analysis? 1. Measure time empirically 2. Do times match BigOh prediction? (d) MaxSumTest (MaxSubSum doubling in size) Suppose F(N) is the correct BigOh function for some algorithm. What should be true about T(N)/F(N) for various values of N? 1. It should converge to some positive constant 2. If it converges to zero, then F(N) is too big 3. If it diverges, then F(N) is too small Remarks on BigOh Analysis ------------------------- Case 1: Consider the following fragment of code. for ( int i = 0; i < n; i++ ) for ( int j = 0; j < i; j++ ) sum++; The inside loop does not always repeat n times. Does this mean the code has a BigOh bound that is smaller than O(N^2)? Case 2: Consider using the same sorting algorithm on the following 2 lists. A = 0 1 2 3 4 9 5 6 7 8 B = 5 9 1 8 0 2 6 4 7 3 Could the algorithm be faster for one of the lists? In general, it is possible for an algorithm to run faster for some inputs than for others. Case 3: Consider sequential search. What's the Big-Oh bound? Unsuccessful search: needs N compares Worst-case successful search: needs N compares Average-case successful search: needs N/2 compares All are O(N) Features and limitations of BigOh analysis: 1. Worst-case vs average-case a. Average-case: average time over all inputs of size N b. Worst-case: longest time over all inputs of size N 2. BigOh does not work for small input sizes 3. Large constants on the dominant term can cause wrong choice 4. Some algorithms require average-case analysis which can be difficult